//
// Created by Administrator on 2023/10/6.
/*
 * GESP 2023.9 四级真题
 * 3.2 编程题 2
试题编号：2023-09-23-04-C-02
试题名称：变长编码
时间限制：1.0 s
内存限制：128.0 MB
3.2.1 问题描述
小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，
生活中很少用到2^31-1 这么大的数，生活中常用的0~100 这种数也同样需要用 4个字节的补码表示，太浪费了些。
热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：
1. 对于给定的正整数，首先将其表达为二进制形式。例如，(0){10}=(0){2} ，(926){10}=(1110011110){2} 。
2. 将二进制数从低位到高位切分成每组 7 bit，不足 7 bit的在高位用 0 填补。例如， (0){2} 变为0000000 的一组，
 (1110011110){2}变为0011110 和0000111 的两组。
3. 由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上1 ，否则在最高位填上 0。于
是， 的变长编码为 一个字节， 的变长编码为 和 两个字节。
这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，987654321012345678
的二进制为(0001101 1011010 0110110 1001011 1110100 0100110 101000 010110 1001110){2}
，于是它的变长编码为（十六进制表示） CE 96 C8 A6 F4 CB B6 DA 0D ，共 9个字节。
你能通过编写程序，找到一个正整数的变长编码吗？
3.2.2 输入描述
输入第一行，包含一个正整数 N。约定0<=N<=10^18 。
3.2.3 输出描述
输出一行，输出 N对应的变长编码的每个字节，每个字节均以 2位十六进制表示（其中， A-F 使用大写字母表示），
两个字节间以空格分隔。
3.2.4 样例输入1
 0
3.2.5 样例输出1
 00
3.2.6 样例输入2
926
3.2.7 样例输出2
 9E 07
3.2.8 样例输入3
 9876543210123456789
3.2.9 样例输出3
CE 96 C8 A6 F4 CB B6 DA 0D
 * */
// 参考官方给的答案

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long n = 926;
//    n=987654321012345678;
//    n = 0;
    if (n == 0)
    {
        cout << "00";
        return 0;
    }
    vector<int> split;
    while (n > 0)
    {
        split.push_back(n & 0b01111111);
        n >>= 7;
    }
    // 除了最后一组高位(第8位)保留零,其他高位都是1
    for (int i = 0; i < split.size() - 1; ++i)
    {
        split[i] |= 0b10000000;
    }
    for (int j = 0; j < split.size(); ++j)
    {
        // 取高(左)四位
        int t = split[j] >> 4;
        // 通过转ASCII码的方式实现bin to hex
        if (t >= 10)
            cout << (char) (t + 'A' - 10);
        else
            cout << (char) (t + '0');
        // 取低(右)四位
        t = split[j] & 0b00001111;
        if (t >= 10)
            cout << (char) (t + 'A' - 10);
        else
            cout << (char) (t + '0');
        // 最后一个后边没有空格
        if (j < split.size() - 1)
            cout << ' ';
    }
    return 0;
}